home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Miscellaneous / Berkeley_db / btree / bt_utils.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  5.7 KB  |  228 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_utils.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/param.h>
  42.  
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46.  
  47. #include <db.h>
  48. #include "btree.h"
  49.  
  50. /*
  51.  * __BT_RET -- Build return key/data pair as a result of search or scan.
  52.  *
  53.  * Parameters:
  54.  *    t:    tree
  55.  *    d:    LEAF to be returned to the user.
  56.  *    key:    user's key structure (NULL if not to be filled in)
  57.  *    data:    user's data structure
  58.  *
  59.  * Returns:
  60.  *    RET_SUCCESS, RET_ERROR.
  61.  */
  62. int
  63. __bt_ret(t, e, key, data)
  64.     BTREE *t;
  65.     EPG *e;
  66.     DBT *key, *data;
  67. {
  68.     register BLEAF *bl;
  69.     register void *p;
  70.  
  71.     bl = GETBLEAF(e->page, e->index);
  72.  
  73.     if (bl->flags & P_BIGDATA) {
  74.         if (__ovfl_get(t, bl->bytes + bl->ksize,
  75.             &data->size, &t->bt_dbuf, &t->bt_dbufsz))
  76.             return (RET_ERROR);
  77.     } else {
  78.         /* Use +1 in case the first record retrieved is 0 length. */
  79.         if (bl->dsize + 1 > t->bt_dbufsz) {
  80.             if ((p = realloc(t->bt_dbuf, bl->dsize + 1)) == NULL)
  81.                 return (RET_ERROR);
  82.             t->bt_dbuf = p;
  83.             t->bt_dbufsz = bl->dsize + 1;
  84.         }
  85.         memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize);
  86.         data->size = bl->dsize;
  87.     }
  88.     data->data = t->bt_dbuf;
  89.  
  90.     if (key == NULL)
  91.         return (RET_SUCCESS);
  92.  
  93.     if (bl->flags & P_BIGKEY) {
  94.         if (__ovfl_get(t, bl->bytes,
  95.             &key->size, &t->bt_kbuf, &t->bt_kbufsz))
  96.             return (RET_ERROR);
  97.     } else {
  98.         if (bl->ksize > t->bt_kbufsz) {
  99.             if ((p = realloc(t->bt_kbuf, bl->ksize)) == NULL)
  100.                 return (RET_ERROR);
  101.             t->bt_kbuf = p;
  102.             t->bt_kbufsz = bl->ksize;
  103.         }
  104.         memmove(t->bt_kbuf, bl->bytes, bl->ksize);
  105.         key->size = bl->ksize;
  106.     }
  107.     key->data = t->bt_kbuf;
  108.     return (RET_SUCCESS);
  109. }
  110.  
  111. /*
  112.  * __BT_CMP -- Compare a key to a given record.
  113.  *
  114.  * Parameters:
  115.  *    t:    tree
  116.  *    k1:    DBT pointer of first arg to comparison
  117.  *    e:    pointer to EPG for comparison
  118.  *
  119.  * Returns:
  120.  *    < 0 if k1 is < record
  121.  *    = 0 if k1 is = record
  122.  *    > 0 if k1 is > record
  123.  */
  124. int
  125. __bt_cmp(t, k1, e)
  126.     BTREE *t;
  127.     const DBT *k1;
  128.     EPG *e;
  129. {
  130.     BINTERNAL *bi;
  131.     BLEAF *bl;
  132.     DBT k2;
  133.     PAGE *h;
  134.     void *bigkey;
  135.  
  136.     /*
  137.      * The left-most key on internal pages, at any level of the tree, is
  138.      * guaranteed by the following code to be less than any user key.
  139.      * This saves us from having to update the leftmost key on an internal
  140.      * page when the user inserts a new key in the tree smaller than
  141.      * anything we've yet seen.
  142.      */
  143.     h = e->page;
  144.     if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
  145.         return (1);
  146.  
  147.     bigkey = NULL;
  148.     if (h->flags & P_BLEAF) {
  149.         bl = GETBLEAF(h, e->index);
  150.         if (bl->flags & P_BIGKEY)
  151.             bigkey = bl->bytes;
  152.         else {
  153.             k2.data = bl->bytes;
  154.             k2.size = bl->ksize;
  155.         }
  156.     } else {
  157.         bi = GETBINTERNAL(h, e->index);
  158.         if (bi->flags & P_BIGKEY)
  159.             bigkey = bi->bytes;
  160.         else {
  161.             k2.data = bi->bytes;
  162.             k2.size = bi->ksize;
  163.         }
  164.     }
  165.  
  166.     if (bigkey) {
  167.         if (__ovfl_get(t, bigkey,
  168.             &k2.size, &t->bt_dbuf, &t->bt_dbufsz))
  169.             return (RET_ERROR);
  170.         k2.data = t->bt_dbuf;
  171.     }
  172.     return ((*t->bt_cmp)(k1, &k2));
  173. }
  174.  
  175. /*
  176.  * __BT_DEFCMP -- Default comparison routine.
  177.  *
  178.  * Parameters:
  179.  *    a:    DBT #1
  180.  *    b:     DBT #2
  181.  *
  182.  * Returns:
  183.  *    < 0 if a is < b
  184.  *    = 0 if a is = b
  185.  *    > 0 if a is > b
  186.  */
  187. int
  188. __bt_defcmp(a, b)
  189.     const DBT *a, *b;
  190. {
  191.     register u_char *p1, *p2;
  192.     register int diff, len;
  193.  
  194.     len = MIN(a->size, b->size);
  195.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
  196.         if (diff = *p1 - *p2)
  197.             return (diff);
  198.     return (a->size - b->size);
  199. }
  200.  
  201. /*
  202.  * __BT_DEFPFX -- Default prefix routine.
  203.  *
  204.  * Parameters:
  205.  *    a:    DBT #1
  206.  *    b:     DBT #2
  207.  *
  208.  * Returns:
  209.  *    Number of bytes needed to distinguish b from a.
  210.  */
  211. int
  212. __bt_defpfx(a, b)
  213.     const DBT *a, *b;
  214. {
  215.     register u_char *p1, *p2;
  216.     register int len;
  217.     int cnt;
  218.  
  219.     cnt = 1;
  220.     len = MIN(a->size, b->size);
  221.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
  222.         if (*p1 != *p2)
  223.             return (cnt);
  224.  
  225.     /* a->size must be <= b->size, or they wouldn't be in this order. */
  226.     return (a->size < b->size ? a->size + 1 : a->size);
  227. }
  228.